\documentclass[E:/GsjzTle/main/main.tex]{subfiles}


\begin{document}

\begin{itemize}
\item
  带权并查集顾名思义就是给集合加上权值
\item
  一般维护\textbf{点到根节点(祖先)的距离}和\textbf{树的大小(集合大小)}
\item
  然后通过两者计算出答案 ( 有点和 \textbf{lca} 类似 ？)
\end{itemize}

\textbf{例题：}

约翰和贝茜在玩一个方块游戏。编号为 \(1\ldots n\) (
\(1 \leq n \leq 30000\) ) 个方块正放在地上，每个构成一个立方柱。\\
游戏开始后，约翰会给贝茜发出 \(P\) (
\(1 \leq P \leq 100000\))个指令。指令有两种：

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  移动（\(M\)）：将包含 \(X\) 的立方柱移动到包含 \(Y\) 的立方柱上。
\item
  询问（\(C\)） ：询问含 \(X\) 的立方柱中，在 \(X\) 下方的方块数目。
\end{enumerate}

\textbf{解：}

\begin{itemize}
\item
  \(far[x]\) 表示 \(x\) 的祖先
\item
  \(dis[x]\) 表示 \(x\) 到根节点的距离
\item
  \(size[x]\) 表示 \(x\) 子树的大小，\(size\) 数组只适用于祖先
\end{itemize}

在将 \(x\) 放在 \(y\) 上后，\(x\) 的祖先成了 \(y\) 集合的新祖先\\
所以有：

\begin{itemize}
\item
  \(far[tx] = ty\)
\item
  \(dis[ty] = size[tx]\)
\item
  \(size[tx] += size[ty]\)
\end{itemize}

而 \(ty\) 子树中的节点的 \(dis\) 此时还未更新\\
它们更新将和路径压缩一并进行\\
即调用到 \(find\) 函数时：

\begin{itemize}
\item
  \(f = far[y]\) (\(f\) 为 \(y\) 的原祖先)
\item
  \(far[y] = find(far[y])\) (将原祖先的祖先更新为新祖先)
\item
  \(dis[y] += dis[f]\) ( \(y\) 到新祖先的距离增加了 \(dis[f]\) )
\end{itemize}

那么 \(X\) 下方的方块数目 \(=\) \(size[F] - dis[X] - 1\) (\(F\) 为 \(X\)
的祖先)

\begin{lstlisting}
int far[N] , size[N] , dis[N];
int find(int x)
{
	if(x == far[x]) return x;
	int t = far[x];   // 原来的根祖先 
	far[x] = find(far[x]); // 根祖先改变 
	dis[x] += dis[t];   // 到新的根祖先的距离  
	return far[x];
}
void Union(int x , int y)
{
	int tx = find(x) , ty = find(y);
	if(tx == ty) return ;
	far[ty] = tx; 
	dis[ty] = size[tx];
	size[tx] += size[ty];
}
void init(int n)
{
	for(int i = 1 ; i <= n ; i ++) far[i] = i , size[i] = 1 , dis[i] = 0;
}
if(op == 'M')
{
	cin >> x >> y; // x 放在 y 上面
	Union(x , y);
}
else
{
	cin >> c;
	int f = find(c);
	cout << size[f] - dis[c] - 1 << '\n';
}
\end{lstlisting}

\end{document}
